import java.util.Arrays;

/**
 * 第一版排序算法的问题
 */
public enum QuickSort implements Sort {
    INSTANCE;

    @Override
    public <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r) return;
        int p = partition(arr, l, r);
        sort(arr, l, p - 1);
        sort(arr, p + 1, r);
    }

    /**
     * @param arr
     * @param l
     * @param r
     * @param <E>
     * @return
     * @循环不变量 arr[l+1...j] `<` v;arr[j+1...i] &gt; v
     */
    private <E extends Comparable<E>> int partition(E[] arr, int l, int r) {

        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i].compareTo(arr[l]) < 0) {
                j++;
                SortingHelper.INSTANCE.swap(arr, j, i);
            }
        }
        SortingHelper.INSTANCE.swap(arr, l, j);
        return j;
    }

    private <E extends Comparable<E>> void printArr(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) {
                System.out.print(",");
            }
        }
    }

    public static void main(String[] args) {
        int n = 1000000;

        Integer[] arr = ArrayGenerator.INSTANCE.generatorRandomArray(n, n);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        System.out.println(" ================================ ");
        SortingHelper.INSTANCE.sortTest(QuickSort.INSTANCE, arr);
        SortingHelper.INSTANCE.sortTest(MergeSort.INSTANCE, arr2);

        arr = ArrayGenerator.INSTANCE.generatorOrderedArray(n);
        arr2 = Arrays.copyOf(arr, arr.length);
        SortingHelper.INSTANCE.sortTest(MergeSort.INSTANCE, arr2);
        SortingHelper.INSTANCE.sortTest(QuickSort3.INSTANCE, arr);
    }
}
